#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/19 13:20
# @Author  : Yuyun
# @File    : 斐波那契数列.py
# @IDE     : PyCharm

#方法①——迭代法
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

#方法②——动态规划
def fib_dp(n):
    #添加此条件，是因为后续dp数组直接初始化dp[0]、dp[1]，故n=0是dp数组越界，需排除此情况
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        #递推公式
        dp[i] = dp[i - 1] + dp[i + 1]
    return dp[n]

#动态规划优化——只维护数组前2个值
def fib_dp_two(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        sum = dp[0] + dp[1]
        dp[0] = dp[1]
        dp[1] = sum
    return dp[1]

#动态规划优化——将数组2个值替换为2个变量，减少内存消耗
def fib_two_var(n):
    if n <= 1:
        return n
    var0, var1 = 0, 1
    for i in range(2, n + 1):
        #类似于数组后一位=前两位之和；然后将为2的窗口向后移动一位
        sum = var0 + var1
        var0 = var1
        var1 = sum
    return var1


if __name__ == '__main__':
    n = int(input())
    # print(fib(n))
    print(fib_dp(n))